package Leetcode.图;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName 省份数量
 * @since: 2023/8/21 14:27
 * @auth: kirito
 * @description:
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
 * 且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 *
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 *
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1
 * 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 *
 * 返回矩阵中 省份 的数量。
 *
 **/
public class 省份数量 {
    //dfs
    public int findCircleNum(int[][] isConnected) {
        int cities = isConnected.length; // 城市的总数
        boolean[] visited = new boolean[cities]; // 记录城市是否被访问过的数组
        int provinces = 0; // 省份的数量

        for (int i = 0; i < cities; i++) {
            if (!visited[i]) { // 如果城市未被访问过
                dfs(isConnected, visited, cities, i); // 进行深度优先搜索
                provinces++; // 省份数量加1
            }
        }

        return provinces; // 返回省份的数量
    }

    public void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
        for (int j = 0; j < cities; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) { // 如果城市i和城市j相连且城市j未被访问过
                visited[j] = true; // 将城市j标记为已访问
                dfs(isConnected, visited, cities, j); // 继续对城市j进行深度优先搜索
            }
        }
    }
    //bfs
    public int findCircleNum2(int[][] isConnected) {
        int cities = isConnected.length; // 城市的总数
        boolean[] visited = new boolean[cities]; // 记录城市是否被访问过的数组
        int provinces = 0; // 省份数量

        Queue<Integer> queue = new LinkedList<Integer>(); // 创建一个队列用于BFS

        for (int i = 0; i < cities; i++) {
            if (!visited[i]) { // 如果城市未被访问过
                queue.offer(i); // 将城市加入队列

                while (!queue.isEmpty()) {
                    int j = queue.poll(); // 取出队列中的当前城市

                    visited[j] = true; // 将当前城市标记为已访问

                    for (int k = 0; k < cities; k++) {
                        if (isConnected[j][k] == 1 && !visited[k]) { // 如果城市j和城市k相连且城市k未被访问过
                            queue.offer(k); // 将城市k加入队列
                        }
                    }
                }

                provinces++; // 省份数量加1
            }
        }

        return provinces; // 返回省份的数量
    }
    //并查集
//    https://leetcode.cn/problems/number-of-provinces/solutions/1975727/li-kou-547-bing-cha-ji-si-lu-jiang-jie-b-u9qh/?envType=study-plan-v2&envId=leetcode-75
    public int findCircleNum3(int[][] isConnected) {
        int cities = isConnected.length; // 城市的总数
        int[] parent = new int[cities]; // 记录城市的父节点

        // 初始化每个城市的父节点为自身
        for (int i = 0; i < cities; i++) {
            parent[i] = i;
        }

        // 遍历每对城市，如果它们相连，则将它们合并
        for (int i = 0; i < cities; i++) {
            for (int j = i + 1; j < cities; j++) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }

        int provinces = 0; // 省份数量

        // 统计根节点数量，即省份的数量
        for (int i = 0; i < cities; i++) {
            if (parent[i] == i) {
                provinces++;
            }
        }

        return provinces; // 返回省份的数量
    }

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2); // 将index1的根节点指向index2的根节点
    }

    public int find(int[] parent, int index) {
        if (parent[index] != index) { // 如果index的父节点不是自身，则递归查找根节点
            parent[index] = find(parent, parent[index]);
        }
        return parent[index]; // 返回根节点的索引
    }

}
